Lemma

Suppose ff is an mm-variate polynomial of degree exactly dd over field 𝔽\mathbb{F}, where ff is not identically zero. Then, the number of zeros of ff is at most d⋅|𝔽|m−1d \cdot | \mathbb{F} |^{m-1}, i.e.

Prx∈𝔽m⁡[f(x)=0]≤d|𝔽|\Pr_{x \in \mathbb{F}^m} [f(x) = 0] \leq \frac{d}{|\mathbb{F}|}

References

  1. J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701–717, 1980.
  2. R. Zippel. Probabilistic algorithms for sparse polynomials. In In Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, pages 216–226, 1979.
  3. Moshkovitz, D. (2010, July). An alternative proof of the Schwartz-Zippel lemma. In Electronic Colloquium on Computational Complexity (ECCC) (Vol. 17, No. 96, p. 34).
  4. https://en.wikipedia.org/wiki/Schwartz–Zippel_lemma
  5. https://cstheory.stackexchange.com/questions/1772/alternative-proofs-of-schwartz-zippel-lemma